Subject: loop detection protocol proposal

From: Choon Lee <[email-masked]>
Date: Wed, 26 Jan 1994 12:53:17 -0800

Hi, fellow looppreventers,

Here's my proposal for a loop detection protocol. Please comment.

Regards,
Choon Lee

Section 0: Background Information
---------------------------------

In the topology of parallel DLSw (multiple DLSw paths between
two LAN segments), multiple DLSw paths can be established, 
resulting in duplicate frames between the end stations.

	|                                |
   X----|                                |----Y
	|  |-----|             |-----|   |
	|--|  J  |-------------|  K  |---|
	|  |-----|             |-----|   |
	|                                |
	|  |-----|             |-----|   |
	|--|  L  |-------------|  M  |---|
	|  |-----|             |-----|   |
	|                                |
    LAN segment A		     LAN segment B

For example, in the above topology, when X sends out a TEST frame,
it gets picked up by both J and L, then sent across the Data Link
Switch to LAN segment B. The TEST response from Y will result in
both DLSw circuits (J-K and L-M) being established. Subsequently,
every frame that X sends out results in 2 frames on LAN segment B,
and vice versa for frames that Y sends out.

With the proposed loop detection scheme, this multiple circuit
(or loop) can be prevented. Before K and M sends out the TEST
frame onto LAN segment B, they each send out a Loop Detection 
frame to discover the existance of alternate path between the
LAN segments. When the DLSw receive the loop detection frame, 
the loop detection ID (which is a tie-breaker) in the frame is 
compared with its own, and the loser will terminate its circuit
establishment process, thus ensuring only one DLSw path between
the LAN segments.

This scheme also prevents loop from forming when the DLSw is across
two bridged segments. E.g., in the diagram above, L-M are assumed
to be datalink bridges. TEST frame will again get to LAN segment
twice. The TEST frame that gets on LAN segment B via the bridges
(i.e. L-M), results in a CANUREACH to flow in the direction of K-J
will result in immediate termination of the DLSw path J-K, due to 
the new DLSw state machines introduced by this scheme.

Section 1: The Loop Detection Proposal
--------------------------------------

The gist of this proposal is as follows:
o when a CANUREACH is received, the DLSw first tries to discover 
  the existance of multiple DLSw paths between the origin and
  target stations.

o if multiple paths exist, the DLSw selects unambiguously the
  DLSw pair to use.

o if the DLSw receives a TEST request on its DLC, followed by a
  CANUREACH from its DLSw partner, it terminates the circuit
  establishment immediately.

o NETBIOS UI frames are examined to determine where it originates
  from, and remembered so that it does not loop indefinitely
  in the network.

This proposal has the following characteristics:
(1) It is a reactive mechanism; it tries to detect the presence
    of a loop only when there is a need to do so.

(2) It does not require the DLSw cloud to be full mesh. It
    assumes that each DLSw has a set of known DLSw partners.

(3) It allows parallel DLSw to exist (parallel DLSw is defined as
    multiple DLSw crcuit between two LAN segments).

(4) It allows DLSw to exist across bridged LAN.

(5) Plug and play. No configuration of DLSw needed, except for
    parameter tuning.

Section 2: Loop Detection PDUs
------------------------------

    I. (12/14 bytes) - MAC header
	    (6 bytes) - DA (see Note 1)
	    (6 bytes) - SA - MAC addr of DLSw that sends out this PDU
	    (2 bytes) - Length (present if 802.3)

	Note 1:
	If Loop Detection Command frame,
	    DA = DLSw functional address (TBD)
	Otherwise (Loop Detection Response frame)
	    DA = MAC address of the DLSw that this PDU is
		 responding to

    II. (3 byte) - LLC header
	    (1 byte) - DSAP (TBD)
	    (1 byte) - DSAP (TBD)
	    (1 byte) - Control (x'03')

    III. (26 bytes) - Loop Detection PDU
	
	+-+-+------+------+-+-+-+---------+
	|a|b|  c   |  d   |e|f|g|    h    |
	+-+-+------+------+-+-+-+---------+

	a (1 byte) - PDU type
	    x'00' - Loop Detection Command
	    x'01' - Loop Detection Response

	b (1 byte) - Version number
	    x'00'

	c (6 bytes) - Target MAC address

	d (6 bytes) - Origin MAC address

	e (1 byte) - Target Link SAP

	f (1 byte) - Origin Link SAP

	g (1 byte) - Loop resolving state
	    x'00' - LOOP_RESOLVING (if DLSw state is LOOP_RESOLVING)
	    x'01' - LOOP_RESOLVED
	    
	h (9 bytes) - Loop Detection Identifier
	  this is a tie-breaker among parallel DLSw to determine
	  which DLSw to use. It is comprised of 2 parts:
	    (1 byte) - priority (0 .. 255)
	    (8 bytes) - IP_addresses
	        computed by concatenation of IP address pair (IP 
	        address of origin and target DLSw), with the smaller 
	        IP address value occupying the first 4 bytes

Section 3: Modification to the DLSw state machine
-------------------------------------------------

(1) New States
	Two new states are proposed:

	CIRCUIT_SEARCHING
	    The DLSw is awaiting a ICANREACH (after sending
	    a CANUREACH), or a NETBIOS_NR (after sending a 
	    NETBIOS_NQ).

	LOOP_RESOLVING
	    The target DLSw is awaiting for expiration of 
	    Loop_Detection timer, upon which time a DLC_START_DL 
	    or NB_Name_Query can be sent to its DLC.

(2) New Events
	LD_TIMER_EXP
	    Expiration of Loop Detection Timer.

	DLC_LD_CMD
	    DLC received a Loop Detection Command.

	DLC_LD_RSP
	    DLC received a Loop Detection Response.

(3) New Actions
	SET_LD_TIMER
	    Start Loop Detection Timer.

	DLC_LD_CMD
	    DLC send a Loop Detection Command.

	DLC_LD_RSP
	    DLC send a Loop Detection Response.

(4) New SSP message
	HALT_CIRCUIT
	    stop this circuit from being established.

(5) State Transition Table
	
	(a) CIRCUIT_SEARCHING
	    -----------------
	Event                Actions            Next State
	-----                -------            ----------
	Receive ICANREACH    Send REACH_ACK,    CIRCUIT_ESTABLISHED
	                     DLC_RESOLVE_R

	Receive NETBIOS_NR   Send REACH_ACK,    CIRCUIT_ESTABLISHED
			     DLC_DGRM

	Receive CANUREACH    Send HALT_CIRCUIT  DISCONNECTED

	DLC_DGRM             Send DATAFRAME
	except                   (note 1)
	NB_Name_Query,
	NB_Name_Response

	Note 1: If the frame source address has been seen previously
		from the same interface, or is seen for the first 
		time, then send DATAFRAME.
		Otherwise, the Netbios datagram is discarded.

	This state is added to the DLSw state machine to differentiate
	from the DISCONNECTED state, for the origin DLSw (the one 
	that is waiting for a ICANREACH). It also allow for immediate 
	termination of circuit establishement when a loop is detected 
	(when CANUREACH is received after DLC_RESOLVE_C had been
	received).

	This state is entered into from DISCONNECTED state, after
	the receipt of DLC_RESOLVE_C, and a CANUREACH is sent.

	For SNA, the CIRCUIT_SEARCHING state is exited upon receipt
	of ICANREACH frame, thereupon a Test response is sent to the
	origin station, and a REACH_ACK sent to the target DLSw.

	For NETBIOS, the state is exited upon receipt of NETBIOS_NR
	frame, thereupon a NB_Name_Recognized frame is sent to the
	origin station, and a REACH_ACK sent to the target DLSw.

	(b) LOOP_RESOLVING
	    --------------
	Event                Actions            Next State
	-----                -------            ----------
	DLC_LD_CMD           DLC_LD_RSP
			         (note 2)       (note 2)

	DLC_LD_RSP           (note 2)           (note 2)

	LD_TIMER_EXP         DLC_START_DL       RESOLVE_PENDING
				 (note 3)

	DLC_DGRM             Send DATAFRAME
	except                   (note 1)
	NB_Name_Query,
	NB_Name_Response

	Note 1: If the frame source address has been seen previously
		from the same interface, or is seen for the first time,
		then send DATAFRAME.
		Otherwise, the Netbios datagram is discarded.

	Note 2: If the PDU's Loop Detection ID (priority + IP address 
		pair) is smaller than the DLSw's, or the PDU's 
		loop_resolving_state has a value of LOOP_RESOLVED, a 
		HALT_CIRCUIT is sent, and the state DISCONNECTED is 
		entered.

	Note 3: For NETBIOS, it is DLC_DGRM (send NB_Name_Query).

	This state is added to the DLSw state machine to allow loop
	detection to precede the actual sending out of TEST or
	NB_Name_Query frame.

	This state is entered into from DISCONNECTED state, after
	the receipt of CANUREACH. It will then attempt to discover
	the existance of multiple DLSw paths between the origin and
	target stations by sending loop detection command frame out 
	its DLC. At the same time, a loop detection timer is activated.

	While in this state, if a loop detection command is received
	(see note 4), a loop detection response (loop_resolving_state 
	set to LOOP_RESOLVING) is returned. 
	
	When a loop detection frame (either loop detection command 
	or loop detection response) is received, a check is made on 
	whether the circuit establishment for the stations should 
	continue. If the PDU has a loop_resolving_state value 
	of LOOP_RESOLVED (indicating that there is currently another 
	path between the stations), or that the PDU's loop_detection_id
	has a smaller value (indicating that another DLSw pair is
	attempting to establish a circuit for the same two stations,
	and that DLSw pair has a better tie-breaker), then this
	circuit should be terminated immediately.

	Note 4: the loop detection PDU is looked at only if these
		4-tuple (DA, SA, DSAP, SSAP) are the same as the circuit.

	(c) DISCONNECTED
	    ------------

	Several state transititons are altered due to the addition
	of the new states. The following state table reflects the
	proposed table for DISCONNECTED state:

	Event                Actions            Next State
	-----                -------            ----------
	Receive CANUREACH    SET_LD_TIMER,      LOOP_RESOLVING
			     DLC_LD_CMD
	Receive NETBIOS_NQ   SET_LD_TIMER,      LOOP_RESOLVING
			     DLC_LD_CMD
	DLC_RESOLVE_C        Send CANUREACH     CIRCUIT_SEARCHING
	DLC_DGRM             If NB_Name_Query:  CIRCUIT_SEARCHING
			     Send NETBIOS_NQ
			     Else:
			     Send DATAFRAME
				 (note 1)
	Receive DATAFRAME    DLC_DGRM
				 (note 2)

	Note 1: If the frame source address has been seen previously
		from the same interface, or is seen for the first time,
		then send DATAFRAME.
		Otherwise, the Netbios datagram is discarded.

	Note 2: If the origin MAC address has been seen previously
		from the same interface, or is seen for the first time,
		then DLC_DGRM.
		Otherwise, the DATAFRAME is discarded.

	(d) RESOLVE_PENDING, CIRCUIT_PENDING
	    --------------------------------

	Add the following new event to deal with receipt of loop
	detection command frame:

	Event                Actions            Next State
	-----                -------            ----------
	DLC_LD_CMD           DLC_LD_RSP
	                         (note 1)

	Note 1: respond with loop_resolving_state set to LOOP_RESOLVED.

Section 4: NETBIOS frames learning
----------------------------------

The Netbios UI frames (NB frames beside NB_Name_Query and
NB_Name_Recognized) can loop indefinitely in a parallel DLSw 
topology. To avoid this from happening, a Netbios table is required
to keep track of the source of such frames. 

For these Netbios UI frames, the source address of the DLC_DGRM (or 
DATAFRAME) are stored in a Netbios address table, together with the 
interface that it is received on. Subsequent NETBIOS UI frames are 
checked against the table. If the interface is different from the 
stored value, the Netbios frame is not propagated.

Each entry in the Netbios table is aged out after they are in the
table for some specific time (time value TBD). The aging mechanism is 
implementation specific.

---

From: [email-masked] (Shannon Nix)
Date: Wed, 09 Feb 94 11:02:53 EST

Choon,

Your proposal looks very good.  I think you are on the right track.

I have only one comment: (perhaps I don't fully understand your proposal)

Am I correct in assuming that a switch implementing this protocol would have
to wait for the LD_TIMER to expire during every connection sequence if there
were no parallel switchs (which also implement the protocol) on the same LAN 
segment with connectivity to the remote station originating the connection?

If so, this would seem to increase the end-to-end connection establishment
time in a fairly common topology in order to acoomodate what is likely to
be a less common topology.

Assuming I've correctly interpreted your proposal, this is something I'd like
to see addressed.  Unfortunately, I don't have any ideas at the moment, having
only just read the proposal in detail.

Rgds, Shannon

---

From: Choon Lee <[email-masked]>
Date: Wed, 9 Feb 1994 13:21:33 -0800

Shannon,

You are correct. The loop detection proposal, in its present form, does
require a loop detection time to be added to the overall connection
establishment time. We can certainly talk about this further in the AIW,
to address this issue.

Regards,
Choon

>> From [email-masked] Wed Feb  9 08:37:35 1994
>> Date: Wed, 09 Feb 94 11:02:53 EST
>> From: [email-masked] (Shannon Nix)
>> To: [email-masked]
>> Subject: Re: loop detection protocol proposal
>> Content-Length: 850
>> 
>> Choon,
>>